import java.util.Arrays;

public class ShellSort {//希尔排序
    public static void sort(int[] arr){
        for (int gap = arr.length >> 1; gap >= 1; gap = gap >> 1){
            for (int low = gap; low < arr.length; low++){
                // 将 low 位置的元素插入至 [0..low-1] 的已排序区域
                int t = arr[low];
                int i = low - gap; // 已排序区域指针
                while (i >= 0 && t < arr[i]){// 没有找到插入位置
                    arr[i+1] = arr[i];
                    i -= gap;
                }
                // 找到插入位置
                if (i != low - gap){
                    arr[i + gap] = t;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {9, 3, 7, 2, 5, 8, 1, 4};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
